import java.util.ArrayList;
import java.util.Iterator;
import java.util.LinkedList;
import java.util.Map;


public class EnhancedPreflow {

private SimpleGraph m_G;
	
	/**m_activeVertex maintains all active vertices*/
	private LinkedList m_activeVertex = new LinkedList();
	
	/**m_maxHeight is the maximum height in m_G*/
	int m_maxHeight;
	
	 private LinkedList[] m_heightActive;
	
	
	public EnhancedPreflow(SimpleGraph graph)
	{
		m_G = graph;
		m_maxHeight = m_G.numVertices();
		m_heightActive = new LinkedList[2*m_maxHeight];
		for(int i =0; i!= 2*m_maxHeight; ++i)
		{
			m_heightActive[i] = new LinkedList();
		}
	}
	
	/**
	 * @param v is a vertex
	 * @param e is a incident edge of vertex v
	 * @return For a given vertex and edge, if the vertex is the start point of edge,
	 * return the forward capacity, otherwise return the backward capacity.
	 */
	public int getEdgeCapacity(Vertex v, Edge e)
	{
		if(e.getFirstEndpoint().equals(v))
			return ((EdgeData)e.getData()).getForwardCapacity();
		else
			return 0-((EdgeData)e.getData()).getBackwardCapacity();
	}
	
	
	/**
	 * Relable the height of vertex v
	 * @param v is a vertex needed to change its height
	 * height(u) = min { height(v) +1 | r(u,v) >0 }
	 */
	public void Relable(Vertex v)
	{
		Iterator incidentEdges = v.incidentEdgeList.iterator();
		int height = m_maxHeight;
		while(incidentEdges.hasNext())
		{
			Edge edge = (Edge)incidentEdges.next();
			EdgeData data = (EdgeData)edge.getData();
			if((edge.getFirstEndpoint().equals(v) && data.getForwardCapacity()>0) ||(edge.getSecondEndpoint().equals(v) && data.getBackwardCapacity() > 0))
			{
				Vertex w = m_G.opposite(v, edge);
				int wHeight = ((VertexData)w.getData()).getHeight();
				if( wHeight < height)
					height = wHeight;
			}			
		}
		height += 1;
		((VertexData)v.getData()).setHeight(height);
		if(height > m_maxHeight)
			m_maxHeight = height;
		m_activeVertex.addLast(v);
		m_heightActive[height].add(v);
	}

	
	public int BFS(Vertex v)
	{
		
		if(v.getName().equals("t"))
		{
			((VertexData)v.getData()).setHeight(0);
			return 0;
		}
		((VertexData)v.getData()).setVisited();
		//change
		int num = m_maxHeight;
		
		LinkedList childVertex = new LinkedList();
		Iterator incidentEdges = v.incidentEdgeList.iterator();
		while(incidentEdges.hasNext())
		{
			Edge e = (Edge) incidentEdges.next();
			if(e.getFirstEndpoint().equals(v))
			{
				Vertex w = e.getSecondEndpoint();
				childVertex.add(w);
			}
		}			
		Iterator child = childVertex.iterator();
		
		while(child.hasNext())
		{
			Vertex c = (Vertex) child.next();
			int i = num;
			if(!((VertexData)c.getData()).isVisited())
				i = BFS(c);
			else
				i = ((VertexData)c.getData()).getHeight();
			if(i < num)
				num = i;
		}
		num += 1;
		if(!(v.getName().equals("s")))
			((VertexData)v.getData()).setHeight(num);
		return num;		
	}
	
	/**
	 * According to the excess value of the current vertex, push flow to its incident edges
	 * @param currentVertex is the current vertex which has excess to push
	 * @return the updated excess value of this currentVertex
	 */
	public int Push(Vertex currentVertex)
	{
		Iterator activeEdges = currentVertex.incidentEdgeList.iterator();
		int exceed = ((VertexData) currentVertex.getData()).getExceedValue();
		while(exceed > 0 && activeEdges.hasNext() )
		{
			Edge pushEdge = (Edge) activeEdges.next();
			Vertex incidentVertex = m_G.opposite(currentVertex, pushEdge);
			int pushValue = getEdgeCapacity(currentVertex,pushEdge);
			if(((VertexData)incidentVertex.getData()).getHeight()< ((VertexData)currentVertex.getData()).getHeight() 
					&& pushValue!= 0 )
			{
				//push flow
				int amount;
				if(pushValue < 0)
					amount = ((EdgeData)pushEdge.getData()).decreaseFlow(exceed);
				else
					amount = ((EdgeData)pushEdge.getData()).increaseFlow(exceed);

				if(!incidentVertex.getName().equals("t") && !incidentVertex.getName().equals("s"))
					((VertexData)incidentVertex.getData()).increaseExceedValue(amount);
				int height = ((VertexData)incidentVertex.getData()).getHeight();
				if(((VertexData)incidentVertex.getData()).isExceed() && !m_activeVertex.contains(incidentVertex))
				{
					m_activeVertex.addLast(incidentVertex);
					m_heightActive[height].add(incidentVertex);
					if(height > m_maxHeight)
						m_maxHeight = height;
				}
				exceed -= amount;				
			}
		}
		((VertexData)currentVertex.getData()).setExceedValue(exceed);
		return ((VertexData)currentVertex.getData()).getExceedValue();
	}
	
	
	/**
	 * Preflow push algorithm
	 * After running this we get the result of a max-flow
	 */
	public int MaxFlow()
	{
		Iterator vertecies = m_G.vertices();
		Vertex source = null;
		//get the source node
		while(vertecies.hasNext())
		{
			source = (Vertex) vertecies.next();
			if(source.getName().equals("s"))
				break;
		}
		if(source == null)
			return 0;
		
//		BFS(source);
		m_maxHeight = 0;		
		//saturate all source edges
		Iterator incidentEdges = source.incidentEdgeList.iterator();
		while(incidentEdges.hasNext())
		{
			Edge edge = (Edge) incidentEdges.next();
			EdgeData edgeData = (EdgeData) edge.getData();
			int flow = edgeData.getCapacity();
			//push flow as capacity in each edge
			((EdgeData)edge.getData()).increaseFlow(flow);
			Vertex incidentVertex = m_G.opposite(source, edge);
			
			//set excess at nodes that is not a source or sink.
			//if the node is active, put it into the FIFO list.
			if(!incidentVertex.getName().equals("t") && !incidentVertex.getName().equals("s"))
				((VertexData) incidentVertex.getData()).setExceedValue(flow);
			int height = ((VertexData)incidentVertex.getData()).getHeight();
			if(((VertexData) incidentVertex.getData()).isExceed()&& !m_activeVertex.contains(incidentVertex))
			{
				m_activeVertex.addLast(incidentVertex);
				m_heightActive[height].addLast(incidentVertex);
				if(height > m_maxHeight)
					m_maxHeight = height;
			}
		}
		
		//While there are active vertices apply one of the basic actions on the vertex
		//read from the vertex with the highest height
		while(!m_activeVertex.isEmpty())
		{
			while(m_heightActive[m_maxHeight].isEmpty() && m_maxHeight >= 0)
			{
				m_maxHeight -= 1;
			}
			if(m_maxHeight < 0)
				return 0;
			Vertex currentVertex = (Vertex)( m_heightActive[m_maxHeight]).pop();
			m_activeVertex.remove(currentVertex);
						
			while(Push(currentVertex) != 0)
			{		
				((VertexData)currentVertex.getData()).increaseHeight();
			}
			
		}
		Iterator result = source.incidentEdgeList.iterator();
		int max_flow = 0;
		while(result.hasNext())
		{
			Edge e = (Edge) result.next();
			max_flow += ((EdgeData)e.getData()).getFlow();
		}
		return max_flow;
	}
}
